COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	start[e84,jmc]		New start for chapter 1
C00012 ENDMK
C⊗;
start[e84,jmc]		New start for chapter 1

	Lisp is a programming language for computing with the
symbolic expressions that arise in artificial intelligence and
in computation with mathematical formulas.  The core of the
language is called pure Lisp and we begin with that.  Pure
Lisp is most clearly explained rather abstractly.  The data
of Lisp are called S-expressions.

	Begin with a set {\it A} called the set of atoms.  For our
present purpose it doesn't matter what the atoms are.  We only
need to provide a test for equality of two atoms and a predicate
for telling whether an object is an atom.
Because we will need parentheses for Lisp S-expressions,
we use square brackets for applying a function to arguments.
Thus we write $\atom[x]$ for the assertion that {\it x} is an
atom.  However, we usually reduce the number
of brackets by omitting them for functions of one argument.  Thus
we simply write $atom x$.

	S-expressions are built up from atoms by the following rule.

	{\it An atom is an S-expression, and an ordered pair of
S-expressions is an S-expression.  All S-expressions are formed
in this way.}

	From this abstract point of view we need say nothing about
how S-expressions are represented in the memory of a computer or
on paper.  We do need names for the basic operations on S-expressions.
The operation that forms pairs is called {\it cons}, and we write
$x \qcons y$ for the operation of making a pair out of the S-expressions
{\it x} and {\it y}.

	Inverse to the operation $\qcons$ thaat forms pairs are the two
operations \qa\ and \qd\ that takes the components of a pair.  These
operations are read {\it car} and {\it cdr} respectively.  The fact
that these operations are inverses is expressed by the equations
%
	$$\qa\ [x\qcons y] = x,$$
%
	$$\qd\ [x\qcons y] = y,$$
%
and
	$$¬atom[x] ⊃ [x = [\qa x] \qcons [\qd x]].$$

	Here we have used the logical symbol ¬ meaning {\it not}
and the logical symbol ⊃ meaning {\it implies}.  We will treat
logical symbolism more fully later.

	We make the the convention that single argument functions
bind more tightly than infixes and relations bind (like equality)
bind more tightly that logical symbols like implication, so the
last equation can be written without brackets as
%
	$$¬atom x ⊃ x = \qa x \qcons \qd x.$$
%
	We need a notation for constant S-expressions.  For the
moment we'll use capital letters for atoms, so that {\sx A},
{\sx B}, etc. denote atoms.  The pairs are formed by surrounding
the paired items by parentheses and separating them with a dot.
Thus {\sx A}, {\sx (A.A)}, {\sx (A.B)} and {\sx ((A.B).(A.(B.C)))}
are all S-expressions.  It is important to distinguish the
operation $\qcons$ that forms S-expressions from
the dot used in writing S-expressions.  The former is an operation
that can be executed, i.e. a program getting {\it x} and {\it y},
computes $x\qcons y$, whatever $x$ and $y$ may be, while {\sx (A.B)}
just denotes that one S-expression.  Of course, we have
%
	$${\sx A}\qcons {\sx B} = {\sx (A.B)},$$
%
but we can't write $(x.y)$ with {\it x} and {\it y} as variables.

	The fact that the pairs are distinct from atoms is
expressed by the formula
%
	$$¬atom[x\qcons y].$$
%
	With what we have so far we can only write trivial facts,
but to check your understanding, notice that the following are
consequences of what we have so far.
%
	$${\sx (B.C)} = \qd{\sx (A.B)}\qcons \qa{\sx (C.D)}.$$
%
	$$atom \qa\qd {\sx (A.(B.C))}$$.
%
	To write pure Lisp programs, we need two more things -
conditional expressions and recursion.

	The expression
%
	$$\qif p \qthen a \qelse b$$
%
is evaluated as follows:

	First evaluate {\it p}.  If {\it p} is true then the value
of the conditonal expression is that of {\it a}.  Otherwise its
value is that of {\it b}.

	Now we can define a simple pure Lisp program for reversing
the \qa-parts and \qd -parts of an S-expression and its subexpressions.
We'll call our function {\it flip}, and we want, for example, that
%
	$$flip {\sx ((A.B).C)} = {\sx (C.(B.A))}.$$
%
	The Lisp program is defined by
%
	$$flip x ← \qif atom x \qthen x \qelse flip \qd x\qcons flip\qa x.$$
%
If you're still shakey on the conventions for omitting brackets, note that
this is equivalent to
%
	$$flip[x] ← [\qif atom[x] \qthen x \qelse flip[\qd[x]]\qcons flip[\qa[x]]].$$